Mi manual de algoritmos/version_actual/src/grafos/ford_fulkerson_sparse.cpp

   1 /////////////// Maximum flow for sparse graphs ///////////////
   2 ///////////////    Complexity: O(V * E^2)      ///////////////
   3
   4 /*
   5   Usage:
   6   Call initialize_max_flow();
   7   Create graph using add_edge(u, v, c);
   8   max_flow(source, sink);
   9
  10   WARNING: The algorithm writes on the cap array. The capacity
  11   is not the same after having run the algorithm.  If you need
  12   to run the algorithm several times on the same graph, backup
  13   the cap array.
  14  */
  15
  16 namespace Flow {
  17     // Maximum number of nodes
  18     const int MAXN = 100;
  19     // Maximum number of edges
  20     // IMPORTANT: Remember to consider the backedges. For
  21     // every edge we actually need two! That's why we have
  22     // to multiply by two at the end.
  23     const int MAXE = MAXN * (MAXN + 1) / 2 * 2;
  24     const int oo = INT_MAX / 4;
  25     int first[MAXN];
  26     int next[MAXE];
  27     int adj[MAXE];
  28     int cap[MAXE];
  29     int current_edge;
  30
  31     /*
  32       Builds a directed edge (u, v) with capacity c.
  33       Note that actually two edges are added, the edge
  34       and its complementary edge for the backflow.
  35      */
  36     int add_edge(int u, int v, int c){
  37       adj[current_edge] = v;
  38       cap[current_edge] = c;
  39       next[current_edge] = first[u];
  40       first[u] = current_edge++;
  41
  42       adj[current_edge] = u;
  43       cap[current_edge] = 0;
  44       next[current_edge] = first[v];
  45       first[v] = current_edge++;
  46     }
  47
  48     void initialize_max_flow(){
  49       current_edge = 0;
  50       memset(next, -1, sizeof next);
  51       memset(first, -1, sizeof first);
  52     }
  53
  54     int q[MAXN];
  55     int incr[MAXN];
  56     int arrived_by[MAXN];
  57     //arrived_by[i] = The last edge used to reach node i
  58     int find_augmenting_path(int src, int snk){
  59       /*
  60         Make a BFS to find an augmenting path from the source
  61         to the sink.  Then pump flow through this path, and
  62         return the amount that was pumped.
  63       */
  64       memset(arrived_by, -1, sizeof arrived_by);
  65       int h = 0, t = 0;
  66       q[t++] = src;
  67       arrived_by[src] = -2;
  68       incr[src] = oo;
  69       while (h < t && arrived_by[snk] == -1){ //BFS
  70         int u = q[h++];
  71         for (int e = first[u]; e != -1; e = next[e]){
  72           int v = adj[e];
  73           if (arrived_by[v] == -1 && cap[e] > 0){
  74             arrived_by[v] = e;
  75             incr[v] = min(incr[u], cap[e]);
  76             q[t++] = v;
  77           }
  78         }
  79       }
  80
  81       if (arrived_by[snk] == -1) return 0;
  82
  83       int cur = snk;
  84       int neck = incr[snk];
  85       while (cur != src){
  86         //Remove capacity from the edge used to reach
  87         //node "cur", and add capacity to the backedge
  88         cap[arrived_by[cur]] -= neck;
  89         cap[arrived_by[cur] ^ 1] += neck;
  90         //move backwards in the path
  91         cur = adj[arrived_by[cur] ^ 1];
  92       }
  93       return neck;
  94     }
  95
  96     int max_flow(int src, int snk){
  97       int ans = 0, neck;
  98       while ((neck = find_augmenting_path(src, snk)) != 0){
  99         ans += neck;
 100       }
 101       return ans;
 102     }
 103 }